'''
动态结构，替罪羊树
'''

class Node:
    def __init__(self, key, value, left=None, right=None, size=1):
        self.key = key
        self.value = value
        self.left = left
        self.right = right
        self.size = size
    def __repr__(self):
        return f'{{key: {self.key}, value: {self.value}, size: {self.size}}}'

class ScapegoatTree:
    def __init__(self, alpha = 0.7):
        self.root = None
        self.alpha = alpha

        # maintain: node 平衡的节点, father: node的父节点, left: node是father的左节点else 右节点
        self.maintain_node = None
        self.maintain_father = None
        self.maintain_left = True

        # collect: 收集需要调整的节点们，以中序遍历； size: 收集了多少个,复用这个数组
        self.collect = []
        self.collect_size = 0

    def _up(self, root):
        root.size = 1 + (root.left.size if root.left else 0) + (root.right.size if root.right else 0)

    def _collect(self, root):
        collect = self.collect
        self.collect_size = 0
        def f(root):
            if root:
                f(root.left)
                collect[self.collect_size] = root
                self.collect_size += 1
                f(root.right)
        if len(collect) < root.size:
            collect += [None] * (root.size - len(collect))
        f(root)

    def _build(self):
        collect = self.collect
        def f(l, r):
            if l > r: return None
            m = l + r >> 1
            collect[m].left = f(l, m-1)
            collect[m].right = f(m+1, r)
            self._up(collect[m])
            return collect[m]
        return f(0, self.collect_size - 1)

    def _rebuild(self):
        maintain_node, maintain_father, maintain_left = self.maintain_node, self.maintain_father, self.maintain_left
        if maintain_node:           # 是否又不平衡
            self._collect(maintain_node)
            if self.collect_size:       # 是否真的不平衡
                if not maintain_father:     # 是否是根节点
                    self.root = self._build()
                elif maintain_left:
                    maintain_father.left = self._build()
                else:
                    maintain_father.right = self._build()

    def _isbalance(self, root):
        return self.alpha * root.size >= max(root.left.size if root.left else 0, root.right.size if root.right else 0)
    def _connect_node(self, father, node, left):
        if not father:
            self.root = node
        elif left:
            father.left = node
        else:
            father.right = node

    def _get(self, root, k):
        if root is None:
            return None
        elif k < root.key:
            return self._get(root.left, k)
        elif k > root.key:
            return self._get(root.right, k)
        return root

    def _add(self, k, v):
        def f(father, root, left):
            if not root:
                self._connect_node(father, Node(k, v), left)
            else:
                if k < root.key:
                    f(root, root.left, True)
                elif k > root.key:
                    f(root, root.right, False)
                else:
                    root.value = v
                self._up(root)
                if not self._isbalance(root):
                    self.maintain_node, self.maintain_father, self.maintain_left = root, father, left

        self.maintain_node, self.maintain_father, self.maintain_left = None, None, None
        f(None, self.root, None)
        self._rebuild()
    def _delete(self, k):
        def f(father, root, left):
            if not root: return
            if k < root.key:
                f(root, root.left, True)
            elif k > root.key:
                f(root, root.right, False)
            else:
                if not root.left:
                    root = root.right
                elif not root.right:
                    root = root.left
                else:
                    most_left = root.right  # 右树的最左节点
                    while most_left.left:
                        most_left = most_left.left
                    root.right = self._delete_most_left(root.right, most_left)
                    most_left.left = root.left
                    most_left.right = root.right
                    root = most_left
                self._connect_node(father, root, left)
            if root:
                self._up(root)
                if not self._isbalance(root):
                    self.maintain_node, self.maintain_father, self.maintain_left = root, father, left

        self.maintain_node, self.maintain_father, self.maintain_left = None, None, None
        f(None, self.root, None)
        self._rebuild()

    def _delete_most_left(self, node, most_left):
        if node == most_left: return most_left.right
        node.left = self._delete_most_left(node.left, most_left)
        self._up(node)
        return node


    # ******************** 基本api ****************************
    def put(self, key, value):
        self._add(key, value)

    def get(self, key):
        target = self._get(self.root, key)
        if not target: raise KeyError(key)
        return target.value

    def remove(self, key):
        self._delete(key)

    def size(self):
        return self.root.size if self.root else 0

    __getitem__ = get
    __setitem__ = put
    __delitem__ = remove
    __len__ = size

    def floor(self, key):
        def f(root):
            if root is None: return float('-inf')
            if key < root.key:
                return f(root.left)
            elif key > root.key:
                return max(root.key, f(root.right))
            else:
                return root.key

        return f(self.root)

    def ceil(self, key):
        def f(root):
            if root is None: return float('inf')
            if key < root.key:
                return min(root.key, f(root.left))
            elif key > root.key:
                return f(root.right)
            else:
                return root.key

        return f(self.root)